package zhengqc.sort;

public class SelectionSort<E extends Comparable<E>> extends Sort<E> {
    public SelectionSort() {
        this.sortName = "SelectionSort";
    }
    public void sort(E[] array) {
        // 循环不变量: array[0~i) 是有序的; array[i~n) 是无序的
        for (int i = 0; i < array.length; ++i) {
            // 选择 array[i~n) 中最小值的索引
            int minIndex = i;
            for (int j = i; j < array.length; ++j) {
                if (array[j].compareTo(array[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }
    private static <E> void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
